The present invention, a method of efficient storage and reconstruction of the codewords of the Extended Hamming Code, relates to pulse or digital communications and, more particularly, to a quantizer or inverse quantizer.
A quantizer is a device for converting numerical data into a finite number of possible outputs. That is, the input to a quantizer may be any value, but the output of a quantizer is limited to only certain values. The function of a quantizer is to determine which of its possible output values is closest to the input value and put out that value. For example, a flip-flop puts out either a voltage equal to the power supply voltage connected to the flip-flop (e.g., five volts or a logic one) or a voltage equal to the ground voltage connected to the flip-flop (e.g., zero volts or a logic zero). The input to a flip-flop may be any value between ground voltage and the power supply voltage. The flip-flop determines which of its two possible output values is closest to the input value and puts out that value. Typically, an input voltage greater than or equal to one-half of the power supply voltage will cause a flip-flop to put out the power supply voltage (i.e., a logic one) while an input voltage below one-half of the power supply voltage will cause a flip-flop to put out the ground voltage (i.e., a logic zero).
Quantizers are used in the design of signals for use over a noisy channel. Analog to Digital converters convert complex analog signals (e.g., 0.654783V) into simplistic digital signals (e.g., logic 1). This is a form of data compression. An area centered at one of the allowable outputs is called a Voronoi region. If the quantizer receives a point in this region, it converts it, if necessary, to the allowable point in the center of the region.
Quantizers come in two types, scalar quantizers and vector quantizers. A scalar quantizer quantizes data from a single source by rounding a real number to its nearest output value (e.g., a flip-flop). A vector quantizer quantizes data from multiple sources by choosing one point from a finite set of points in n-dimensional space that is closest to the point represented by the input vector. A point in n-dimensional space is simply a string of n real numbers. That is, x=(x1, x2, x3, . . . , xn). For example, a point in three dimensional space is a point represented by three coordinates, a point in four dimensional space is a point represented by four coordinates, and so on. The allowed output values of a vector quantizer are called centroids.
The present invention concerns a lattice quantizer. A lattice in n-dimensional space is defined as follows. Let (v1, v2, . . . , vn) be a set of n linearly independent vectors in n-dimensional space. The lattice generated by (v1, v2, . . . , vn) is the set (c1v1+c2v2+ . . . +cnvn), where c1, . . . , cn are integers. The vectors v1, v2, . . . , vn form a basis for the lattice. If x=(x1, x2, . . . , xn) then the norm of x is equal to (x12+x22+ . . . +xn2). A sphere in n-dimensional space with center u=(u1, u2, . . . , un) and radius p consists of all the points x=(x1, x2, x3, . . . , xn) satisfying (x1xe2x88x92u1)2+(x2xe2x88x92u2)2+ . . . +(xnxe2x88x92un)2=p2. A sphere packing is described by specifying the centers u and the radius p. When the centers of a group of spheres form a lattice, the packing is referred to as lattice packing. Lattice packing always has a center at a point designated as an origin with the remaining centers on concentric spheres or shells around the origin. The shells are numbered according to their proximity to the center or origin point. That is, the shell closest to the origin point is shell 1; the shell second closest to the origin point is shell 2, and so on. If one lattice may be obtained from another by rotation, reflection, or change of scale then it is said that the lattices are equivalent or similar.
Mathematicians continue to look for dense packings of n-dimensional spheres because there are important practical applications of sphere packing to problems arising in digital communications. A finite subset of the points on the surface of a sphere is called a spherical code. Spherical codes may be constructed from sphere packings. The sphere packing density of a lattice is defined by the number of spheres that fit within a particular volume. The kissing number of a lattice is defined as the number of spheres that a sphere in the lattice touches. The 8-dimensional lattice, designated as E8, has the highest sphere packing density and the highest possible kissing number in eight dimensions.
In a lattice quantizer, the centroids are grid points in n-dimensional space. The advantage of using a lattice quantizer is that the centroids are already known and do not have to be calculated from the input data. The disadvantage of using a lattice quantizer is that there are an infinite number of centroids. Because of this, lattice quantizers are only appropriate for quantizing data that has a probability distribution that is heavily concentrated around a single point in n-dimensional space (e.g., the origin).
Quantizing introduces error. The magnitude of the error is the distance from the received point to the acceptable point. The acceptable points are chosen to minimize the error, or more precisely, to minimize the mean squared error. For various dimensions, the mean squared error has been determined.
Quantizers may be used to design signals for data transmission or storage systems (e.g., error correcting codes). A code is a set of signals to be transmitted. Only these codes will be transmitted over a channel. The members of a code are designed to be easily distinguished from the other members of the code even in the presence of noise. Noise may corrupt a particular member of the code, but it is intended that the corrupted code will be identified as the particular code that was transmitted. So, a message to be sent is encoded, sent over a noisy channel, and decoded to recover the message.
Certain important lattices include the cubic lattice Zn, the root lattices (i.e., An, Dn, E6, E7, and E8), the Coxeter-Todd lattice K12, the sixteen dimensional Barnes-Wall lattice, the 24 dimensional Leech lattice, and their duals. The best quantizers are achieved using these lattices in their respective dimensions.
U.S. Pat. No. 5,150,209, entitled xe2x80x9cHIERARCHICAL ENTROPY CODED LATTCE THRESHOLD QUANTIZATION ENCODING METHOD AND APPARATUS FOR IMAGE AND VIDEO COMPRESSION,xe2x80x9d discloses an eight dimensional lattice quantizer based on the E8 lattice that requires the storage of 920 points to encode and decode 2400 points that do not round to the origin point but instead round to a codeword in either shell 1 or shell 2. A reduction in storage from 2400 to 920 (i.e., a 60% improvement) is achieved using the quantizer of U.S. Pat. No. 5,150,209. The present invention uses a rotated equivalent lattice to improve upon the quantizer of U.S. Pat. No. 5,150,209 by reducing even further the number of points that are stored to encode and decode 2400 points that do not round to the origin point. The present invention reduces the number of codewords that must be stored to 16 in the Extended Hamming Code form or in an alternate extended quadratic residue code form to one codeword. This is a 98% reduction in required codeword storage, or when using the alternate extended quadratic residue code form an approximate 99.9% reduction, over the method of U.S. Pat. No. 5,150,209.
U.S. Pat. No. 5,150,209 is hereby incorporated by reference into the specification of the present invention.
In three articles authored by John H. Conway and N. J. A. Sloane, entitled xe2x80x9cFast 4- and 8-Dimensional Quantizers and Decoders,xe2x80x9d IEEE, 1981, pp. F4.2.1-F4.2.4, xe2x80x9cFast Quantizing and Decoding Algorithms for Lattice Quantizers and Codes,xe2x80x9d IEEE Transactions on Information Theory, Vol. IT-28, No. 2, March 1982, and xe2x80x9cSoft Decoding Techniques for Codes and Lattices, including the Golay Code and the Leech Lattice,xe2x80x9d IEEE Transactions on Information Theory, Vol. IT-32, No. 1, January 1986, mathematical techniques associated with lattice quantizers are disclosed but the present invention, which minimizes the storage requirement and the computational complexity of an eight dimensional lattice quantizer, is not disclosed therein.
It is an object of the present invention to minimize the storage requirement of an eight-dimensional lattice quantizer.
It is another object of the present invention to require only the storage of sixteen eight-bit words, {square root over (2)}, 1/{square root over (2)}, two tables, and a parity-check matrix in an eight-dimensional lattice quantizer and to reduce the required number of stored eight-bit words to one when using the alternate extended quadratic residue code form of the quantizer.
It is another object of the present invention to minimize the computational complexity of an eight-dimensional lattice quantizer.
It is another object of the present invention to minimize the computational complexity of an eight-dimensional lattice quantizer by requiring only multiplication by {square root over (2)}, replacement of 1s by 1/{square root over (2)}, replacement of 2s by {square root over (2)}, and a matrix multiplication.
The present invention is a method of lattice quantization that minimizes the storage requirement and the computational complexity of an eight dimensional lattice quantizer. The idea is to quantize a data point so that it may be transmitted error-free in a noisy channel and reduce bandwidth. This is accomplished, in the Extended Hamming Code form of the invention, by transmitting a data point in the form of information that indicates a codeword of the Extended Hamming Code that is closest to the data point along with information that would allow a receiver to modify the codeword in order to reconstruct the desired data point. The specific steps of the method of the present invention are as follows.
The first step is to acquire an eight dimensional data point.
The second step is to multiply each coordinate of the data point by the square root of two to form an inflated data point.
The third step is to round each coordinate of the inflated data point to the nearest integer to form a rounded and inflated data point.
The fourth step is to find the modulo-two reduction for the absolute value of each coordinate of the rounded and inflated data point to form an initial codeword. If none of the coordinates of the initial codeword are in error then the initial codeword is one of sixteen codewords of the eight-bit Extended Hamming Code. Such a codeword may or may not be equivalent to the rounded and inflated data point. If the codeword is not equivalent to the rounded and inflated data point then additional information, as described below, will be provided to allow a receiver to start with the codeword, modify it according to the additional information in order to recover the rounded and inflated data point, and then deflate the rounded and inflated data point in order to recover a data point that is the closest allowable data point that the lattice quantizer could produce from the acquired data point.
The fifth step is to multiply a parity-check matrix of the eight-bit Extended Hamming Code by the initial codeword. The result of this step is four bits, commonly referred to as a syndrome, that indicate whether or not the initial codeword is error free. The eight-bit Extended Hamming Code allows for the detection and correction of one-bit errors and the detection, but not the correction, of two-bit errors. The present invention improves upon the features of the eight-bit Extended Hamming Code by a method that detects and corrects for both one-bit errors and two-bit errors.
If the result of step five is all-zeros then the initial codeword is error-free and is a codeword of the eight-bit Extended Hamming Code. A signal packet representing the codeword and information required to make any modifications to the codeword in order to reconstruct the rounded and inflated data point on which the codeword was derived is then sent to the receiver. In a subsequent step, the receiver will then recover the intended data point from the recovered rounded and inflated data point. The steps for generating and sending a signal packet are described below.
If the top-most bit of the result of step five is a 1 then one of the binary bits of the initial codeword is wrong. Since the initial codeword is based on the rounded and inflated data point then the bit location in the rounded and inflated data point that corresponds to the bit location in the initial codeword is also wrong. Therefore, the error bit must be corrected in both the rounded and inflated data point and the initial codeword. The corrected rounded and inflated data point will then be the point that is nearest the intended inflated data point. The corrected rounded and inflated data point will indicate what additional information, if any, must be transmitted to the receiver in order for the receiver to reconstruct the rounded and inflated data point from the codeword. The corrected initial codeword will then match one of the sixteen codewords in the Extended Hamming Code. Information representing the corrected codeword will be sent to the receiver in order to allow the receiver to recover the corrected codeword. The other three bits of the result of step five indicate which coordinate in the rounded and inflated data point and which bit in the initial codeword are in error. The error coordinate in the initial codeword is corrected by flipping that bit (i.e., changing a 0 to a 1 or changing a 1 to a 0). The error bit in the rounded and inflated data point is corrected by replacing its value with the value obtained from rounding the opposite way from how that coordinate was originally rounded. For example, if the error coordinate in the rounded and inflated data point is a 1.0 that was based on an inflated data point of 1.3 then the correction would be 2.0. That is, 1.3 originally rounded to the nearest integer 1.0. Since this is in error, then 1.3 should have been rounded the other way to the next closest integer (i.e., 2.0). The error in the rounded and inflated data point, and in the initial codeword, is corrected. Data representing the corrected codeword, and any other information necessary to reconstruct the rounded and inflated data point, is then transmitted to the receiver.
If the top-most bit of the result of step five is a 0 and at least one of the other three bits is a 1 then two of the positions in the rounded and inflated data point and in the initial codeword are wrong. That is, two of the positions in the rounded and inflated data point, and two bits in the initial codeword, must be changed. As above, the corrected rounded and inflated data point yields a point closest to the inflated data point while the corrected codeword yields a codeword in the eight-bit Extended Hamming Code. The other three bits of the result of step five are used to determine which two bits in the rounded and inflated data point and in the initial codeword are wrong. After the two bit locations in the rounded and inflated data point and the initial codeword are identified, the bits in error are corrected as described above. Data representing the corrected codeword and any other information necessary to reconstruct the rounded and inflated data point is then transmitted to the receiver.
The present invention, in the Extended Hamming Code form, stores a table, in both the transmitter and the receiver, that contains the sixteen eight-bit codewords of the eight-bit, or eight-dimensional, Extended Hamming Code. These sixteen codewords are used to represent the 2400 data points in shell 1 and shell 2. This compares very favorably to the 920 codewords stored in U.S. Pat. No. 5,150,209 in order to represent the same number of data points in shell 1 and shell 2. The transmitter and receiver may also store a table that indicates where two 2s may be located in a rounded and inflated data point. Instead of storing a table to identify the location of two 2s, the locations may be determined from an equation representing a particular table construction. The transmitter also stores a parity-check matrix for the eight-bit Extended Hamming Code and the square root of two. The transmitter multiplies the acquired data point by the square root of two in order to form an inflated data point. The transmitter also multiplies the parity-check matrix by the initial codeword. The receiver stores either 1/{square root over (2)} or 1/{square root over (2)} and {square root over (2)}.
In order for the receiver to deflate an inflated data point the receiver either multiplies each coordinate of the inflated data point by 1/{square root over (2)} or replaces each 1 by 1/{square root over (2)} and each 2 by {square root over (2)}. The polarity of the 1s and 2s are also taken into account by setting a polarity bit accordingly. By using the replacement approach, the equivalent of multiplication is achieved more efficiently.
To further reduce codeword storage requirements in the alternate extended quadratic residue code form of the invention, the initial codeword of the eight-bit Extended Hamming Code may be transformed into an equivalent extended quadratic residue code form of the Extended Hamming Code. This extended quadratic residue code form has the property that any weight-four codeword can be obtained from any other weight-four codeword through circularly shifting 7 of its 8 bits, leaving one bit fixed, or the complement of the codeword resulting from such a shift. Because any weight-four codeword can be obtained from any other codeword only one codeword need be stored. Instead of transmitting the position of the codeword in the eight-bit Extended Hamming Code table, as in the Extended Hamming Code form of the invention, information on the number of circular shifts required to obtain the desired extended quadratic residue codeword and a bit to indicate whether the initial codeword was complemented before transformation is transmitted.
To transmit a representation of an all-0s codeword in shell 1, and information necessary to modify the codeword in order to recover the rounded and inflated data point, on which it is based, nine bits are transmitted. Four bits indicate the position in the eight-bit Extended Hamming Code table where the codeword may be found in the Extended Hamming Code form or constitute a special code indicating that the codeword is the all-0s codeword in the alternate extended quadratic residue code form. The receiver initially sets the rounded and inflated data point equal to the codeword and then modifies it according to the other information transmitted in order to reconstruct the intended rounded and inflated data point if different. The other information includes, one bit to indicate that the rounded and inflated data point is in shell 1, three bits to indicate which bit in the rounded and inflated data point should be a 2, and one bit to indicate the polarity of the 2. In order to recover the intended data point each 2 in the recovered rounded and inflated data point is replaced with {square root over (2)}.
To transmit a representation of an all-0s codeword in shell 2, and information necessary to modify the codeword to the rounded and inflated data point on which it is based, twelve bits are transmitted. Four bits indicate the position in the eight-bit Extended Hamming Code table where the codeword may be found in the Extended Hamming Code form or constitute a special code indicating that the codeword is the all-0s codeword in the alternate extended quadratic residue code form. Again, the receiver initially sets the rounded and inflated data point equal to the codeword and then modifies it according to the other information sent in order to reconstruct the intended rounded and inflated codeword. The other information includes, one bit to indicate that the rounded and inflated data point is in shell 2, five bits to indicate the position in a table that tells the receiver which two bits in the inflated data point are 2s, one bit to indicate the polarity of the first 2, and one bit to indicate the polarity of the second 2. In order to recover the intended data point each 2 in the recovered rounded and inflated data point is replaced with {square root over (2)} of the same polarity.
To transmit a representation of an all-1""s codeword in shell 2, and information necessary to modify it in order to recover the intended rounded and inflated data point, twelve bits are transmitted. The rounded and inflated data point is initially set to the intended codeword and the codeword is modified according to the additional information in order to recover the intended rounded and inflated data point. The rounded and inflated data point is then deflated in order to recover the intended data point. That is, four bits indicate the position in the eight-bit Extended Hamming Code table where the codeword may be found in the Extended Hamming Code form or constitute a special code indicating that the codeword is the all-1s codeword in the alternate extended quadratic residue code form, one bit indicates the polarity of the first 1 in the rounded and inflated data point, one bit indicates the polarity of the second 1 in the rounded and inflated data point, one bit indicates the polarity of the third 1 in the rounded and inflated data point, one bit indicates the polarity of the fourth 1 in the rounded and inflated data point, one bit indicates the polarity of the fifth 1 in the rounded and inflated data point, one bit indicates the polarity of the sixth 1 in the rounded and inflated data point, one bit indicates the polarity of the seventh 1 in the rounded and inflated data point, and one bit indicates the polarity of the eighth 1 in the rounded and inflated data point. In order to recover the intended data point, each 1 in the recovered rounded and inflated data point is replaced with 1/{square root over (2)} of the same polarity.
To transmit a representation of a weight-four codeword in shell 1, and information necessary to modify the codeword in order to recover the intended rounded and inflated data point, nine bits are transmitted. That is, four bits indicate the position in the eight-bit Extended Hamming Code table where the codeword may be found in the Extended Hamming Code form or the number of circular shifts required and whether the codeword need be complemented to obtain the desired extended quadratic residue codeword in the alternate extended quadratic residue code form, one bit indicates that the rounded and inflated data point is in shell 1, one bit indicates the polarity of the first 1 in the rounded and inflated data point, one bit indicates the polarity of the second 1 in the rounded and inflated data point, one bit indicates the polarity of the third 1 in the rounded and inflated data point, and one bit indicates the polarity of the fourth 1 in the rounded and inflated data point. In order to recover the intended data point, each 1 in the recovered rounded and inflated data point is replaced with 1/{square root over (2)} of the same polarity.
To transmit a representation of a weight-four codeword in shell 2, and information necessary to modify the codeword in order to recover the intended rounded and inflated data point, twelve bits are transmitted. That is, four bits indicate the position in the eight-bit Extended Hamming Code table where the codeword may be found in the Extended Hamming Code form or the number of circular shifts required and whether the codeword need be complemented to obtain the desired extended quadratic residue codeword in the alternate extended quadratic residue code form, one bit indicates that the rounded and inflated data point is in shell 2, one bit indicates the polarity of the first 1 in the rounded and inflated data point, one bit indicates the polarity of the second 1 in the rounded and inflated data point, one bit indicates the polarity of the third 1 in the rounded and inflated data point, one bit indicates the polarity of the fourth 1 in the rounded and inflated data point, two bits to indicate which coordinate in the rounded and inflated data point must be a 2, and one bit indicates the polarity of the 2. In order to recover the intended data point, each 1 in the recovered rounded and inflated data point is replaced with of the same polarity, and each 2 in the recovered rounded and inflated data point is replaced with 1/{square root over (2)} of the same polarity.
A signal packet that represents a codeword which is based on a rounded and inflated data point that is closest to the inflated data point, and information necessary to modify the codeword in order to reconstruct the rounded and inflated data point, is then transmitted to a receiver in either the Extended Hamming Code or alternate extended quadratic residue code form of the invention. The receiver decodes the signal packet in order to reconstruct the intended codeword, reconstruct the rounded and inflated data point from the intended codeword, and recovers the intended data point from the rounded and inflated data point. Note that the receiver need store only the table of sixteen codewords of the eight-bit Extended Hamming Code or one codeword of the extended quadratic residue code, a table that lists the twenty-eight different ways that two 2s may appear in a rounded and inflated data point, 1/{square root over (2)}, and {square root over (2)}. In an alternate embodiment, the 2s-position table may be replaced by a function that represents the equation of a suitable 2s-position table.
The aforementioned features, objects, and advantages of this method over the prior art will become apparent to those skilled in the art from the following detailed description and accompanying drawings.